package leetbook.hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class Solution380 {

    public static void main(String[] args) {

        //Your RandomizedSet object will be instantiated and called as such:
        RandomizedSet obj = new RandomizedSet();
        System.out.println(obj.insert(1));
        System.out.println(obj.remove(1));
        System.out.println(obj.insert(1));
    }

}

class RandomizedSet {

    HashMap<Integer,Integer> hashMap; //存储key和可以1在keys里面的下标
    ArrayList<Integer> keys;
    Random rand;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        hashMap = new HashMap<>();
        keys = new ArrayList<>();
        rand = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(!hashMap.containsKey(val)){
            keys.add(val);
            hashMap.put(val,keys.size()-1);
            return true;
        }
        return false;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(hashMap.containsKey(val)){
            //把最后一个元素覆盖掉要删除的val
            int delIdx = hashMap.get(val); //val在keys里的下标
            int lastKey = keys.get(keys.size()-1);//keys里最后一个元素的值
            keys.set(delIdx,lastKey); //keys里最后一个元素把要删除的val的位置替换掉
            keys.remove(keys.size()-1); //keys里最后一个元素可以删除了
            //可能出现删除的本身就是keys里最后一个元素，所以以下两句顺序要注意
            hashMap.put(lastKey,delIdx);//hashMap里更新最后一个元素的下标
            hashMap.remove(val);//hashMap里删除val的Node
            return true;
        }
        return false;
    }

    /** Get a random element from the set.
     * 用一个ArrayList保存所有的key，随机生成[0,arr.size)内的数字
     * */
    public int getRandom() {
        int i = rand.nextInt(keys.size());
        return keys.get(i);
    }
}